package com.zecan.dijkstra;

import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/14
 * \* Time: 11:38
 * \* Description:
 * \
 */
public class DijkstraTest {
    public static void main(String[] args) {
        final int N = 65535;
        char[] vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] martrix = new int[][]{
                {N, 5, 7, N, N, N, 2}, {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N}, {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4}, {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N}};
        Graph graph = new Graph(vertex, martrix);
        graph.showGraph();
        graph.dsj(6);
    }
}


class Graph {
    private char[] vertex; // 存放顶点信息
    private int[][] martrix; // 存放邻接矩阵信息
    private VisitedVertex visitedVertex;
    public Graph(char[] vertex, int[][] martrix) {
        this.vertex = vertex;
        this.martrix = martrix;
    }

    public void showGraph() {
        for (int[] arr : martrix) {
            System.out.println(Arrays.toString(arr));
        }
    }

    public void dsj(int index) {
        visitedVertex = new VisitedVertex(vertex.length, index);
        updata(index);
        for(int i = 1 ; i < vertex.length; i++) {
            int j = visitedVertex.updateArr();
            updata(j);
        }
    }

    public void updata (int index) {
        int len = 0; // 记录当前顶点到另一个顶点的长度总和
        for (int i = 0; i < martrix[index].length; i++) {
            len = visitedVertex.getDis(index) + martrix[index][i]; // 获取初始顶点到当前结点与当前结点的邻接结点的长度
            if(!visitedVertex.inVisit(i) && len < visitedVertex.getDis(i)) {
                //如果当前顶点的邻接结点没有访问过 且 len 小于 初始顶点到邻接结点长度
                visitedVertex.upDataDis(i,len);
                visitedVertex.upDataPre(i,index);
            }
        }
    }
}

class VisitedVertex {
    // 记录各个顶点是否访问过 1 表示访问过 0 未访问
    public int[] alreadyArr;
    // 每个下标对应的值为前一个顶点下标
    public int[] preVisited;
    //记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到其他顶点的距离
    //最短距离就会被存放到dis中
    public int[] dis;

    /**
     * @param length 传递过来的顶点的个数
     * @param index  从哪个顶点开始进行扫描
     * @return
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    public VisitedVertex(int length, int index) {
        this.alreadyArr = new int[length];
        this.preVisited = new int[length];
        this.dis = new int[length];
        Arrays.fill(dis, 65535);
        this.alreadyArr[index] = 1;
        dis[index] = 0; //将要从index开始的顶点设置路程为0
    }

    /**
     * 查找当前index 下标的顶点是否已访问
     *
     * @param index 需要查找的顶点下标
     * @return 如果已经访问过 则返回 true  未访问则返回 false
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    public boolean inVisit(int index) {
        return alreadyArr[index] == 1;
    }

    /**
     * 当前方法的作用是 传递index 将其的路程更新
     *
     * @param index 需要更新的顶点的下标
     * @param len   传递过来的路程
     * @return
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    public void upDataDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 将index下标的顶点的前驱顶点设定为pre
     *
     * @param index 需要更改前驱的index
     * @param pre   前驱顶点
     * @return
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    public void upDataPre(int index, int pre) {
        preVisited[index] = pre;
    }

    public int getDis(int index) {
        return dis[index];
    }
    /**
     * 此方法的作用是查找初始顶点的最小顶点的值
     * @param  
     * @return 返回初始顶点的最小邻接顶点的下标
     * @author 
     * @creed: Talk is cheap,show me the code
     * @date  
     */
    public int updateArr() {
        int index = 0, minLen = 65535;
        //当前循环的作用是——> 从 dis[i] 中查找初始顶点附近的最小的顶点的值
        for (int i = 0; i < alreadyArr.length; i++) {
            // 如果当前顶点没有被访问过，且 其值小于最小值
            if(alreadyArr[i] != 1 && dis[i] < minLen) {
                minLen = dis[i];
                index = i;
            }
        }
        alreadyArr[index] = 1; //  将此次找出的最小的顶点设为已访问
        return index;
    }
}
